Recent trends in social networks include the rise of businesses that manage social networking websites (e.g., Facebook, MySpace, Twitter) where users can freely post their data (images, text, files, etc.) and share it with their friends, peers, or anyone else having access to the website. As the most popular sites are currently attracting tens of millions of users, consequences of site misuses are being documented on a daily basis in major newspapers and media entities. One typical class of misuse is that users happen to share various types of sensitive data (e.g., embarrassing images, politically incorrect opinions, proprietary files, etc.), which trigger undesired consequences (e.g., impacting decisions with respect to job hiring and firing, provision of medical or other types of insurance, etc.).
Balancing the users' desire of sharing their data (referred to as “utility”) with the users' needs to keep data private against future undesired consequences (referred to as “privacy”) is recognized as a big problem in practical social networks.
Theoretically, users could maintain privacy at the expense of utility (i.e., by sharing no data), or could maximize utility at the expense of privacy (i.e., by not restricting access to all shared data), or, perhaps the best theoretical compromise, could balance utility and privacy by constantly implementing an access control policy which provides the desired data privacy at current and future times. The latter approach, if possible at all, is expected to be impractical for at least two reasons: drafting a policy that is guaranteed to keep privacy in the future may be hard in many scenarios (i.e., data seeming innocent today may not be so tomorrow) and requiring users of a huge social network to perfectly comply to a probably complex privacy policy may have little success in many scenarios, possibly going against the social network's goals. In fact, even in the case of a perfectly complying single user, this user's privacy can be compromised by other users' behavior. Overall, this implies that user-regulated access control alone may not be an acceptable privacy solution.
Recently there have been general discussions of trust and privacy problems with the use of social networks. Moreover, public press is devoting daily attention to these problems, typically writing about undesired events resulting from weak privacy, but occasionally also writing about quick and practical “common sense” ways to limit privacy loss. A few research papers have recently attempted solutions to different privacy problems in social networks. For instance, privacy-preserving criminal investigations were studied in Kerschbaum, F. and Schaad, A. Privacy-preserving social network analysis for criminal investigations, In Proc. of the 7th ACM Workshop on Privacy in the Electronic Society. WPES '08. ACM, New York, N.Y., 9-14; privacy characterizations were studied in Krishnamurthy, B. and Wills, C. Characterizing Privacy in Online Social Networks. In Proc. of ACM WOSN 2008; privacy in graph-based models were studied in Korolova, A., Motwani, R., Nabar, S. U., and Xu, Y. 2008, Link privacy in social networks. In Proceeding of the 17th ACM Conference on Information and Knowledge Management. CIKM '08. ACM, New York, N.Y., 289-298; and a game theory mechanism that promotes truthfulness while sharing data was proposed in Squicciarini, A. C., Shehab, M., and Paci, F. 2009. Collective privacy management in social networks. In Proceedings of the 18th international Conference on World Wide Web. WWW '09. ACM, New York, N.Y., 521-530.